/*
 * @lc app=leetcode.cn id=315 lang=javascript
 *
 * [315] 计算右侧小于当前元素的个数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */

/**
 * 超时
 */
/**
  var countSmaller = function(nums) {
    if(nums.length === 0) return [];
    if(nums.length === 1) return [0];
    let p1 =  0, p2, result = [];
    while(p1 < nums.length){
      p2 = p1 + 1;
      let total = 0;
      while(p2 < nums.length){
        if(nums[p2] < nums[p1]) total++;
        p2++;
      }
      result.push(total)
      p1++;
    }
    return result;
  };
*/

var countSmaller = function(nums) {
  if(nums.length === 0) return [];
  if(nums.length === 1) return [0];
  
  let resArr = [];
  let objArr = [];

  for (let i = 0; i < nums.length; i++) { 
    const ele = nums[i]; 
    let obj = { num: ele, index: i };
    resArr.push(0);
    objArr.push(obj); 
  }

  sliceNums(objArr);
  return resArr;

  // 对 objArr 排序
  function sliceNums (objNums){
    if(objNums.length === 1) return objNums;
    let mid = objNums.length >> 1;

    // 左侧已排序
    let left = sliceNums(objNums.slice(0, mid));
    // 右侧已排序
    let right = sliceNums(objNums.slice(mid, nums.length));
    // 跨左右排序
    return merge(left, right)
  }

  function merge(left, right){
    let tmp = []; // 排序后的数组
    let total = 0; // 统计左大于右的数量
    
    while(left.length || right.length){
      if(!left.length || (right.length && left[0].num > right[0].num)){
        tmp.push(right[0]);
        right.shift();
        total++;
      } else {
        resArr[left[0].index] += total;
        tmp.push(left[0]);
        left.shift();
      }
    }
    return tmp;
  }
};
// @lc code=end

